﻿/*

 * Copyright (c) 2013 Diorge Brognara, Renan Peixoto

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

using System;
using System.Collections.Generic;
using System.Linq;

namespace Grafos {
    /// <summary>
    /// Representa um grafo qualquer
    /// </summary>
    public class Grafo {

        /// <summary>
        /// Conjunto de vértices do grafo
        /// </summary>
        protected Dictionary<string, Vértice> Vértices { get; set; }
        /// <summary>
        /// Conjunto de arestas do grafo
        /// </summary>
        protected HashSet<Aresta> Arestas { get; set; }

        /// <summary>
        /// Instancia um novo grafo, com um conjunto vazio de vértices e arestas
        /// </summary>
        public Grafo() {
            Vértices = new Dictionary<string, Vértice>();
            Arestas = new HashSet<Aresta>();
        }

        /// <summary>
        /// Diz quantas arestas há no grafo
        /// </summary>
        public virtual int QuantidadeArestas {
            get {
                return Arestas.Count;
            }
        }

        /// <summary>
        /// Diz quantos vértices há no grafo
        /// </summary>
        public int QuantidadeVértices {
            get {
                return Vértices.Count;
            }
        }


        /// <summary>
        /// Adiciona um novo vértice ao grafo
        /// </summary>
        /// <param name="v">Vértice a ser adicionado</param>
        /// <exception cref="DuplicateNameException">Já existe um vértice com este nome no grafo</exception>
        /// <remarks>Um grafo não pode ter vértices com nomes repetidos</remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice(new Vértice("A"));
        /// g.AdicionarVértice(new Vértice("A")); // causa erro
        /// </code>
        /// </example>
        public void AdicionarVértice(Vértice v) {
            if (Vértices.ContainsKey(v.Nome))
                throw new DuplicateNameException("Já existe um vértice com este nome no grafo");
            Vértices.Add(v.Nome, v);
        }

        /// <summary>
        /// Adiciona um novo vértice ao grafo
        /// </summary>
        /// <param name="nome">Nome único do vértice a ser adicionado</param>
        /// <exception cref="DuplicateNameException">Já existe um vértice com este nome no grafo</exception>
        /// <remarks>Um grafo não pode ter vértices com nomes repetidos</remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A");
        /// g.AdicionarVértice("B");
        /// g.AdicionarVértice("B"); // causa erro
        /// </code>
        /// </example>
        public void AdicionarVértice(string nome) {
            AdicionarVértice(new Vértice(nome));
        }

        /// <summary>
        /// Adiciona uma coleção de vértices ao grafo
        /// </summary>
        /// <param name="nomes">Nomes únicos dos vértices a serem adicionados</param>
        /// <exception cref="DuplicateNameException">Já existe um vértice com este nome no grafo</exception>
        /// <remarks>Um grafo não pode ter vértices com nomes repetidos</remarks>
        /// <example>
        /// Funcional:
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C", "D", "E");
        /// </code>
        /// Não-funcional:
        /// <code>
        /// g.AdicionarVértice("A", "B", "C", "A");
        /// </code>
        /// </example>
        public void AdicionarVértice(params string[] nomes) {
            foreach (string s in nomes) {
                AdicionarVértice(s);
            }
        }

        /// <summary>
        /// Busca um vértice pelo seu nome
        /// </summary>
        /// <param name="nome">Nome do vértice procurado</param>
        /// <returns>Um vértice com o determinado nome</returns>
        /// <exception cref="ArgumentException">O nome passado como parâmetro não é um vértice do grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A");
        /// Vértice v = g.BuscarVértice("A");
        /// g.AdicionarVértice(v); // causa erro de duplicata de nome
        /// </code>
        /// </example>
        public Vértice BuscarVértice(string nome) {
            if (!Vértices.ContainsKey(nome))
                throw new ArgumentException("Nome inexistente");
            return Vértices[nome];
        }

        /// <summary>
        /// Adiciona uma nova aresta ao grafo
        /// </summary>
        /// <param name="a">Aresta a ser adicionada</param>
        /// <exception cref="ArgumentException">Uma das extremidades da aresta não é vértice do grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// Aresta a = new Aresta(new Vértice("A"), new Vértice("B"));
        /// g.AdicionarAresta(a);
        /// </code>
        /// </example>
        public virtual void AdicionarAresta(Aresta a) {
            if (!Vértices.ContainsKey(a.Extremidade1.Nome) || !Vértices.ContainsKey(a.Extremidade2.Nome))
                throw new ArgumentException("Aresta adicionada deve possuir vértices dentro do grafo");
            Arestas.Add(a);
        }

        /// <summary>
        /// Adiciona uma nova aresta pelo nome de dois vértices
        /// </summary>
        /// <param name="v1">Nome do vértice de uma extremidade</param>
        /// <param name="v2">Nome do vértice de uma extremidade</param>
        /// <exception cref="ArgumentException">Um dos nomes passados como parâmetro não é um vértice do grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B");
        /// g.AdicionarAresta("A", "B");
        /// </code>
        /// </example>
        public virtual void AdicionarAresta(string v1, string v2) {
            AdicionarAresta(BuscarVértice(v1), BuscarVértice(v2));
        }

        /// <summary>
        /// Adiciona uma nova aresta ao grafo
        /// </summary>
        /// <param name="v1">Uma das extremidades da nova aresta</param>
        /// <param name="v2">Uma das extremidades da nova aresta</param>
        /// <exception cref="ArgumentException">V1 ou V2 não pertencem ao grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// Vértice v1 = new Vértice("A");
        /// Vértice v2 = new Vértice("B");
        /// g.AdicionarVértice(v1);
        /// g.AdicionarVértice(v2);
        /// g.AdicionarAresta(v1, v2);
        /// </code>
        /// </example>
        public virtual void AdicionarAresta(Vértice v1, Vértice v2) {
            if (!Vértices.ContainsKey(v1.Nome))
                throw new ArgumentException("V1 não pertence ao grafo");
            if (!Vértices.ContainsKey(v2.Nome))
                throw new ArgumentException("V2 não pertence ao grafo");
            Arestas.Add(new Aresta(v1, v2));
        }

        /// <summary>
        /// Adiciona um conjunto de arestas ao grafo
        /// </summary>
        /// <param name="arestas">Coleção de arestas</param>
        /// <remarks>
        /// Cada par (string, string) representa uma aresta que liga as extremedidades de dado nome
        /// Caso ocorra um erro na inserção de uma aresta, todas as arestas anteriores serão adicionadas, e as posteriores, abortadas
        /// </remarks>
        /// <exception cref="ArgumentException">Um dos nomes passados como parâmetro não é um vértice do grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.AdicionarAresta(new Tuple&lt;string, string&gt;("A", "B"), new Tuple&lt;string, string&gt;("B", "C"));
        /// </code>
        /// </example>
        public virtual void AdicionarAresta(params Tuple<string, string>[] arestas) {
            foreach (Tuple<string, string> a in arestas) {
                AdicionarAresta(a.Item1, a.Item2);
            }
        }

        /// <summary>
        /// Remove um vértice do grafo, e as arestas relacionadas
        /// </summary>
        /// <param name="v">Nome do vértice a ser removido</param>
        /// <remarks>
        /// Remove:
        /// 1. o vértice do grafo
        /// 2. todas as arestas do grafo que possuem o vértice como extremidade
        /// 3. de todos as arestas removidas, remove a aresta do registro de cada um dos dois vértices
        /// </remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.AdicionarAresta("A", "B");
        /// g.AdicionarAresta("A", "C");
        /// g.RemoverVértice("C");
        /// // g.QuantidadeVértices = 2
        /// // g.QuantidadeArestas = 1
        /// // g.BuscarVértice("A").Vizinhança() = {B}
        /// // g.BuscarVértice("C").Vizinhança() = { }
        /// </code>
        /// </example>
        public void RemoverVértice(string v) {
            Vértice vert = Vértices[v];
            Vértices.Remove(v);
            foreach (Aresta a in vert.GetArestas()) {
                Arestas.Remove(a);
                a.Extremidade1.RemoverAresta(a);
                a.Extremidade2.RemoverAresta(a);
            }
        }

        /// <summary>
        /// Diz se há no grafo uma aresta paralela
        /// </summary>
        /// <param name="a">Aresta a ser verificada</param>
        /// <returns>True caso haja uma aresta paralela</returns>
        /// <remarks>
        /// Atalho para mandar um dos vértices da aresta procurar uma aresta até o outro
        /// É necessário que haja uma aresta paralela a A, mas DIFERENTE DE A, no grafo
        /// </remarks>
        /// <exception cref="ArgumentException">A não pertence ao grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// Vértice v1 = new Vértice("A");
        /// Vértice v2 = new Vértice("B");
        /// Aresta a = new Aresta(v1, v2);
        /// g.AdicionarVértice(v1);
        /// g.AdicionarVértice(v2);
        /// g.AdicionarAresta(a);
        /// g.PossuiArestaParalela(a); // false
        /// g.PossuiArestaParalela(v1, v2); // true
        /// </code>
        /// </example>
        public virtual bool PossuiArestaParalela(Aresta a) {
            if (!Arestas.Contains(a))
                throw new ArgumentException("A não está no grafo");
            return a.Extremidade1.ProcurarArestas(a.Extremidade2).Count > 1;
        }

        /// <summary>
        /// Diz se há no grafo uma aresta paralela
        /// </summary>
        /// <param name="v1">Uma das extremidades da suposta aresta</param>
        /// <param name="v2">Uma das extremidades da suposta aresta</param>
        /// <returns>True caso haja uma aresta paralela</returns>
        /// <remarks>Atalho para mandar um dos vértices procurar uma aresta até o outro</remarks>
        /// <exception cref="ArgumentException">V1 ou V2 não pertencem ao grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// Vértice v1 = new Vértice("A");
        /// Vértice v2 = new Vértice("B");
        /// Aresta a = new Aresta(v1, v2);
        /// g.AdicionarVértice(v1);
        /// g.AdicionarVértice(v2);
        /// g.AdicionarAresta(a);
        /// g.PossuiArestaParalela(a); // false
        /// g.PossuiArestaParalela(v1, v2); // true
        /// </code>
        /// </example>
        public bool PossuiArestaParalela(Vértice v1, Vértice v2) {
            if (!Vértices.ContainsKey(v1.Nome))
                throw new ArgumentException("V1 não está no grafo");
            if (!Vértices.ContainsKey(v2.Nome))
                throw new ArgumentException("V2 não está no grafo");
            return v1.ProcurarAresta(v2) != null;
        }

        /// <summary>
        /// Diz se há no grafo uma aresta paralela
        /// </summary>
        /// <param name="v1">Nome de uma das extremidades da suposta aresta</param>
        /// <param name="v2">Nome de uma das extremidades da suposta aresta</param>
        /// <returns>True caso haja uma aresta paralela</returns>
        /// <exception cref="ArgumentException">V1 ou V2 não são nomes de vértices no grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.AdicionarAresta("A", "B");
        /// g.PossuiArestaParalela("A", "B"); // true
        /// g.PossuiArestaParalela("A", "C"); // false
        /// </code>
        /// </example>
        public virtual bool PossuiArestaParalela(string v1, string v2) {
            return BuscarVértice(v1).ProcurarAresta(BuscarVértice(v2)) != null;
        }

        /// <summary>
        /// Calcula quantos componentes conexos há no grafo
        /// </summary>
        /// <param name="ciclo">Se qualquer um dos componentes possui ciclo (ou seja, o grafo possui ciclo, sem contar loops)</param>
        /// <returns>Quantos componentes conexos existem no grafo</returns>
        /// <remarks>É utilizado o algoritmo de busca em largura</remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// bool ciclo;
        /// g.AdicionarVértice("A", "B", "C", "D");
        /// g.AdicionarAresta("A", "B");
        /// g.AdicionarAresta("B", "A")
        /// g.AdicionarAresta("C", "D");
        /// int conexos = g.ComponentesConexos(out ciclo);
        /// // conexos = 2
        /// // ciclo = true
        /// </code>
        /// </example>
        public int ComponentesConexos(out bool ciclo) {
            int componentes = 0;
            Grafo resto = this.Cópia();
            bool háCiclos;
            ciclo = false;

            while (resto.QuantidadeVértices > 0) {
                // faz uma busca em largura no grafo, a partir de um ponto qualquer
                resto.BuscaEmLargura(resto.Vértices.Values.ToArray()[0], out resto, out háCiclos);
                componentes++;
                ciclo = ciclo || háCiclos;
            }

            return componentes;
        }

        /// <summary>
        /// Calcula quantos componentes conexos há no grafo
        /// </summary>
        /// <returns>Quantos componentes conexos existem no grafo</returns>
        /// <remarks>É utilizado o algoritmo de busca em largura</remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C", "D");
        /// g.AdicionarAresta("A", "D");
        /// int conexos = g.ComponentesConexos(); // 3
        /// </code>
        /// </example>
        public int ComponentesConexos() {
            bool b;
            return ComponentesConexos(out b);
        }

        /// <summary>
        /// Diz se o grafo possui pelo menos um loop
        /// </summary>
        /// <returns>True caso haja algum loop no grafo, false caso contrário</returns>
        /// <example>
        /// Com loop:
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B");
        /// g.AdicionarAresta("A", "A");
        /// g.PossuiLoop(); // true
        /// </code>
        /// Sem loop:
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B");
        /// g.AdicionarAresta("A", "B");
        /// g.AdicionarAresta("B", "A");
        /// g.AdicionarAresta("A", "B");
        /// g.PossuiLoop(); // false
        /// g.PossuiCiclo(); // true
        /// </code>
        /// </example>
        public virtual bool PossuiLoop() {
            foreach (Aresta a in Arestas) {
                if (a.ÉLoop)
                    return true;
            }
            return false;
        }


        /// <summary>
        /// Diz se o grafo possui pelo menos um ciclo
        /// </summary>
        /// <returns>True caso haja algum ciclo, false caso contrário</returns>
        /// <remarks>
        /// Utiliza o algoritmo de busca em largura
        /// Loops são ciclos
        /// Arestas paralelas são ciclos
        /// </remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.PossuiCiclo(); // false
        /// g.AdicionarAresta("A", "B");
        /// g.AdicionarAresta("A", "C");
        /// g.PossuiCiclo(); // false
        /// g.AdicionarAresta("A", "C");
        /// g.PossuiCiclo(); // true
        /// </code>
        /// </example>
        public bool PossuiCiclo() {
            bool ret;
            ComponentesConexos(out ret);
            ret =  ret || PossuiLoop();
            return ret;
        }

        /// <summary>
        /// Diz se o grafo satisfaz as propriedades de uma árvore
        /// </summary>
        /// <returns>True caso o grafo satisfaça as propriedades</returns>
        /// <remarks>
        /// As propriedades são: não possui ciclo, e |E| = |V| - 1
        /// </remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C"); // ÉÁrvore = false
        /// g.AdicionarAresta("A", "B"); // ÉÁrvore = false
        /// g.AdicionarAresta("A", "C"); // ÉÁrvore = true
        /// g.AdicionarAresta("A", "B"); // ÉÁrvore = false
        /// </code>
        /// </example>
        public bool ÉÁrvore() {
            return !PossuiCiclo() && QuantidadeArestas == QuantidadeVértices - 1;
        }

        /// <summary>
        /// Realiza uma busca em largura no grafo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <param name="restante">Grafo restante da busca, ou seja, a parte do grafo desconexa ao ponto de partida</param>
        /// <param name="encontrouCiclo">Diz se a pesquisa encontrou algum ciclo ao gerar a árvore</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <remarks>
        /// Se o grafo for desconexo, o parâmetro por referência "restante" possui a parte desconexa da árvore gerada
        /// O parâmetro encontrouCiclo não garante que o grafo não há ciclos, somente que o componente conexo que a árvore engloba não há ciclos
        /// Ou seja, para validar existência ou não de ciclos, é necessário aplicar Buscas em Largura até que o restante seja vazio
        /// </remarks>
        /// <exception cref="ArgumentException">Caso o vértice de partida (raíz) não pertença ao grafo</exception>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// Grafo resto;
        /// bool teveCiclo;
        /// g.AdicionarVértice("A", "B", "C", "D");
        /// g.AdicionarAresta("A", "B");
        /// g.AdicionarAresta("A", "C");
        /// g.AdicionarAresta("B, "D");
        /// g.AdicionarAresta("B", "C");
        /// g.AdicionarAresta("C", "D");
        /// Árvore a = g.BuscaEmLargura(g.BuscarVértice("A"), out resto, out teveCiclo);
        /// // resto = grafo vazio
        /// // teveCiclo = true
        /// // a = (A-B, A-C, B-D) ou (A-B, A-C, C-D)
        /// </code>
        /// </example>
        public virtual Árvore BuscaEmLargura(Vértice partida, out Grafo restante, out bool encontrouCiclo) {
            if (!Vértices.ContainsValue(partida))
                throw new ArgumentException("Vértice de partida da busca não pertence ao grafo");

            Vértice u;
            Grafo g = this.Cópia();
            restante = new Grafo();
            Queue<Vértice> Q = new Queue<Vértice>();
            List<Vértice> rest = new List<Vértice>(), vertArvore = new List<Vértice>(), vizinhança;
            const int branco = 0, cinza = 1, preto = 2;
            int i;

            encontrouCiclo = false;

            foreach (Vértice v in g.Vértices.Values) {
                v.Tag = branco;
                v.λ = float.PositiveInfinity;
                v.π = null;
                rest.Add(v);
            }
            partida = g.BuscarVértice(partida.Nome);
            partida.Tag = cinza;
            partida.λ = 0;
            partida.π = null;
            Q.Enqueue(partida);

            while (Q.Count > 0) {
                u = Q.Dequeue();
                rest.Remove(u);
                vertArvore.Add(u);
                vizinhança = u.Vizinhança();
                foreach (Vértice v in vizinhança) {
                    if ((int)v.Tag == branco) {
                        v.Tag = cinza;
                        v.λ = u.λ + 1;
                        v.π = u;
                        Q.Enqueue(v);
                    } else if ((int)v.Tag == cinza) {
                        encontrouCiclo = true;
                    }
                }
                u.Tag = preto;
            }

            for (i = 0; i < rest.Count; i++) {
                restante.AdicionarVértice(new Vértice(rest[i].Nome));
            }

            foreach (Aresta a in g.Arestas) {
                if ((int)a.Extremidade1.Tag == branco) {
                    restante.AdicionarAresta(restante.BuscarVértice(a.Extremidade1.Nome), restante.BuscarVértice(a.Extremidade2.Nome));
                }
            }

            return Árvore.GerarDePredecessores(vertArvore, false);
        }

        /// <summary>
        /// Realiza a busca em largura, omitindo o grafo restante e se foi encontrado ciclo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <see cref="BuscaEmLargura(Vértice, out Grafo, out bool)"/>
        public virtual Árvore BuscaEmLargura(Vértice partida) {
            Grafo resto;
            bool ciclos;
            return BuscaEmLargura(partida, out resto, out ciclos);
        }
        
        /// <summary>
        /// Realiza a busca em largura, omitindo se foi encontrado ciclo
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <param name="resto">Grafo restante da busca, ou seja, a parte do grafo desconexa ao ponto de partida</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <see cref="BuscaEmLargura(Vértice, out Grafo, out bool)"/>
        public virtual Árvore BuscaEmLargura(Vértice partida, out Grafo resto) {
            bool ciclos;
            return BuscaEmLargura(partida, out resto, out ciclos);
        }

        /// <summary>
        /// Realiza a busca em largura, omitindo o grafo restante
        /// </summary>
        /// <param name="partida">Ponto de partida</param>
        /// <param name="ciclos">Diz se a pesquisa encontrou algum ciclo ao gerar a árvore</param>
        /// <returns>Uma árvore que representa o caminho percorrido pela busca em largura</returns>
        /// <see cref="BuscaEmLargura(Vértice, out Grafo, out bool)"/>
        public virtual Árvore BuscaEmLargura(Vértice partida, out bool ciclos) {
            Grafo resto;
            return BuscaEmLargura(partida, out resto, out ciclos);
        }

        /// <summary>
        /// Cria uma cópia do grafo, copiando todos os vértices e arestas
        /// </summary>
        /// <returns>Um grafo idêntico a este, mas com ponteiros diferentes (duplicação de memória)</returns>
        /// <remarks>
        /// A cópia é profunda. Nenhum trecho de memória é compartilhado
        /// </remarks>
        /// <example>
        /// <code>
        /// Grafo g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// Grafo g2 = g.Cópia();
        /// g2.BuscarVértice("A").Equals(g.BuscarVértice("A")); // false, são ponteiros distintos
        /// </code>
        /// </example>
        public virtual Grafo Cópia() {
            Grafo g = new Grafo();

            foreach (Vértice v in Vértices.Values) {
                Vértice novo = new Vértice(v.Nome);
                novo.Lambda = v.Lambda;
                novo.Pi = v.Pi;
                novo.Tag = v.Tag;
                g.AdicionarVértice(novo);
            }

            foreach (Vértice v in g.Vértices.Values) {
                if (v.Pi != null)
                    v.Pi = g.Vértices[v.Pi.Nome];
            }

            foreach (Aresta a in Arestas) {
                Aresta nova = new Aresta(a.Nome, g.Vértices[a.Extremidade1.Nome], g.Vértices[a.Extremidade2.Nome]);
                g.AdicionarAresta(nova);
            }


            return g;
        }

        /// <summary>
        /// Gera um grafo completo, a partir dos vértices presentes neste grafo
        /// </summary>
        /// <returns>Um grafo Kn, onde N é o número de vértices deste grafo</returns>
        /// <remarks>O grafo original não é alterado</remarks>
        public virtual Grafo GerarKN() {
            Grafo g = new Grafo();

            foreach (Vértice v in Vértices.Values) {
                Vértice novo = new Vértice(v.Nome);
                novo.Lambda = v.Lambda;
                novo.Pi = v.Pi;
                novo.Tag = v.Tag;
                g.AdicionarVértice(novo);
            }

            foreach (Vértice v in g.Vértices.Values) {
                foreach (Vértice v2 in g.Vértices.Values) {
                    // v != v2 e não há aresta entre v e v2 ainda
                    if ((!v.Equals(v2)) && v.ProcurarAresta(v2) == null) {
                        g.AdicionarAresta(v, v2);
                    }
                }
            }

            return g;
        }

        /// <summary>
        /// Gera uma matriz de adjacência a partir deste grafo
        /// </summary>
        /// <param name="nomes">Lista de nomes dos vértices</param>
        /// <param name="matriz">Matriz de adjacência que indica presença ou não de aresta</param>
        /// <remarks>O grafo é considerado grafo básico simples</remarks>
        /// <example>
        /// <code>
        /// Grafo g;
        /// string[] n;
        /// bool[,] m;
        /// 
        /// g = new Grafo();
        /// g.AdicionarVértice("A", "B", "C");
        /// g.AdicionarAresta("A", "A");
        /// g.AdicionarAresta("A", "B");
        /// g.AdicionarAresta("B", "C");
        /// g.GerarMatrizDeAdjacencia(n, m);
        /// // n: "A", "B", "C"
        /// // matriz: { false, true, false,
        /// //           true, false, true,
        /// //           false, true, false }
        /// </code>
        /// </example>
        public void GerarMatrizDeAdjacencia(out string[] nomes, out bool[,] matriz) {
            int i, j;
            int count;

            count = Vértices.Count;
            nomes = new string[count];
            matriz = new bool[count, count];

            for (i = 0; i < count; i++) {
                nomes[i] = Vértices.ElementAt(i).Value.Nome;
                for (j = 0; j < count; j++) {
                    if(i != j)
                        matriz[i, j] = Vértices.ElementAt(i).Value.ProcurarAresta(Vértices.ElementAt(j).Value) != null;
                }
            }
        }

        /// <summary>
        /// Gera um grafo a partir de uma matriz de adjacência
        /// </summary>
        /// <param name="nomes">Nomes dos vértices</param>
        /// <param name="matriz">Matriz de adjacência</param>
        /// <returns>Um grafo determinado pela matriz de adjacência</returns>
        /// <exception cref="ArgumentException">A quantidade de nomes deve ser igual ao tamanho da matriz, e as duas dimensões da matriz devem ser iguais</exception>
        /// <remarks>
        /// Onde a matriz indicar true, há uma aresta. Onde for false, não há aresta
        /// Como a matriz é simétrica, somente a parte inferior é avaliada.
        /// </remarks>
        /// <example>
        /// <code>
        /// string[] nomes = new string[] { "A", "B", "C" };
        /// bool[,] matriz = new bool[,] {
        ///     {0, 1, 0},
        ///     {1, 0, 1},
        ///     {0, 1, 0}
        /// };
        /// Grafo g = Grafo.GerarDeMatrizDeAdjacencia(nomes, matriz);
        /// // g possui os vértices A, B e C, e as arestas A-B e B-C
        /// </code>
        /// </example>
        public static Grafo GerarDeMatrizDeAdjacencia(string[] nomes, bool[,] matriz) {

            if (nomes.Length != matriz.GetLength(0) || nomes.Length != matriz.GetLength(1))
                // transitividade: matriz.GetLength(0) != matriz.getLength(1)
                throw new ArgumentException("Tamanho dos vetores de entrada incorreto");

            int i, j;
            Grafo g = new Grafo();
            foreach (string s in nomes) {
                g.AdicionarVértice(new Vértice(s));
            }

            for (j = 1; j < matriz.GetLength(1); j++) {
                for (i = 0; i < j; i++) {
                    if (matriz[i, j])
                        g.AdicionarAresta(g.BuscarVértice(nomes[i]), g.BuscarVértice(nomes[j]));
                }
            }

            return g;
        }

    }
}
